"""
2940. 找到 Alice 和 Bob 可以相遇的建筑
困难
相关标签
premium lock icon
相关企业
提示
给你一个下标从 0 开始的正整数数组 heights ，其中 heights[i] 表示第 i 栋建筑的高度。

如果一个人在建筑 i ，且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ，那么这个人可以移动到建筑 j 。

给你另外一个数组 queries ，其中 queries[i] = [ai, bi] 。第 i 个查询中，Alice 在建筑 ai ，Bob 在建筑 bi 。

请你能返回一个数组 ans ，其中 ans[i] 是第 i 个查询中，Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ，Alice 和 Bob 不能相遇，令 ans[i] 为 -1 。



示例 1：

输入：heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
输出：[2,5,-1,5,2]
解释：第一个查询中，Alice 和 Bob 可以移动到建筑 2 ，因为 heights[0] < heights[2] 且 heights[1] < heights[2] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[0] < heights[5] 且 heights[3] < heights[5] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Alice 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[3] < heights[5] 且 heights[4] < heights[5] 。
第五个查询中，Alice 和 Bob 已经在同一栋建筑中。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。
示例 2：

输入：heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
输出：[7,6,-1,4,6]
解释：第一个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[0] < heights[7] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 6 ，因为 heights[3] < heights[6] 且 heights[5] < heights[6] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Bob 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 4 ，因为 heights[3] < heights[4] 且 heights[0] < heights[4] 。
第五个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[1] < heights[6] 。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。


提示：

1 <= heights.length <= 5 * 104
1 <= heights[i] <= 109
1 <= queries.length <= 5 * 104
queries[i] = [ai, bi]
0 <= ai, bi <= heights.length - 1
"""
from typing import List

class SegmentTree:
    def __init__(self, arr, default=0):
        # 线段树维护一个长为 n 的数组（下标从 0 到 n-1）
        # arr 可以是 list 或者 int
        # 如果 arr 是 int，视作数组大小，默认值为 default
        if isinstance(arr, int):
            arr = [default] * arr
        n = len(arr)
        self._n = n
        self._tree = [0] * (2 << (n - 1).bit_length())
        self._build(arr, 1, 0, n - 1)

    # 合并两个 val
    def _merge_val(self, a: int, b: int) -> int:
        return max(a, b)  # **根据题目修改**

    # 合并左右儿子的 val 到当前节点的 val
    def _maintain(self, node: int) -> None:
        self._tree[node] = self._merge_val(self._tree[node * 2], self._tree[node * 2 + 1])

    # 用 a 初始化线段树
    # 时间复杂度 O(n)
    def _build(self, a: List[int], node: int, l: int, r: int) -> None:
        if l == r:  # 叶子
            self._tree[node] = a[l]  # 初始化叶节点的值
            return
        m = (l + r) // 2
        self._build(a, node * 2, l, m)  # 初始化左子树
        self._build(a, node * 2 + 1, m + 1, r)  # 初始化右子树
        self._maintain(node)

    def _update(self, node: int, l: int, r: int, i: int, val: int) -> None:
        if l == r:  # 叶子（到达目标）
            # 如果想直接替换的话，可以写 self._tree[node] = val
            self._tree[node] = self._merge_val(self._tree[node], val)
            return
        m = (l + r) // 2
        if i <= m:  # i 在左子树
            self._update(node * 2, l, m, i, val)
        else:  # i 在右子树
            self._update(node * 2 + 1, m + 1, r, i, val)
        self._maintain(node)

    def _query(self, node: int, l: int, r: int, ql: int, qr: int) -> int:
        """
        寻找ql,qr区间的最大值(未实现找第一个>=x的功能)，node,l,r只是内部递归使用，不作为传参
        :param node:
        :param l:
        :param r:
        :param ql:
        :param qr:
        :return:
        """
        #不一定需要完全遍历到叶子节点，比如当前计算的是数组的最大值，比如[3,4,1]那么直接首次返回顶点4即可，不需要遍历到叶子，因为4下面的所有叶子都包含在[ql,qr]
        if ql <= l and r <= qr:  # 当前子树完全在 [ql, qr] 内，返回当前的就是最大值
            return self._tree[node]
        m = (l + r) // 2
        #分了一半，但是发现要查找的元素全在左边
        if qr <= m:  # [ql, qr] 在左子树
            return self._query(node * 2, l, m, ql, qr)
        #分了一半，但是发现要查找的元素全在右
        if ql > m:  # [ql, qr] 在右子树
            return self._query(node * 2 + 1, m + 1, r, ql, qr)
        #左右树都存在寻找的位置，找个最大的
        l_res = self._query(node * 2, l, m, ql, qr)
        r_res = self._query(node * 2 + 1, m + 1, r, ql, qr)
        return self._merge_val(l_res, r_res)

    def _querFirstLarge(self, node: int, l: int, r: int, ql: int, qr: int,target: int) -> int:
        """
        找到ql,qr区间第一个>=target的数
        :param node:
        :param l:
        :param r:
        :param ql:
        :param qr:
        :param target:
        :return:
        """
        #如果当前最大还小，直接返回
        if self._tree[node]<=target:
            return -1
        #遍历到叶子节点
        if l==r:
            # self._tree[node] = -1 #如果不能重复拿同一个数字，则赋值-1
            return l
        m = (l+r)//2
        #分了一半，但是发现要查找的元素全在左边
        if qr <= m:  # [ql, qr] 在左子树
            return self._querFirstLarge(node * 2, l, m, ql, qr,target)
        #分了一半，但是发现要查找的元素全在右
        if ql > m:  # [ql, qr] 在右子树
            return self._querFirstLarge(node * 2 + 1, m + 1, r, ql, qr,target)
        #优先找左边,如果左边找得到就不需要找右边了
        res = self._querFirstLarge(node * 2, l, m, ql, qr,target)
        if res == -1:
            #左边没找到找右边
            res = self._querFirstLarge(node * 2+1, m+1, r, ql, qr,target)
        #如果不能重复拿同一个数字,则需要更新当前的最大值
        # self._maintain(node)
        return res
    def querFirstLarge(self,ql: int, qr: int,target: int) -> int:
        return self._querFirstLarge(1,0,self._n -1,ql,qr,target)

    # 更新 a[i] 为 _merge_val(a[i], val)
    # 时间复杂度 O(log n)
    def update(self, i: int, val: int) -> None:
        self._update(1, 0, self._n - 1, i, val)

    # 返回用 _merge_val 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
    # 时间复杂度 O(log n)
    def query(self, ql: int, qr: int) -> int:
        return self._query(1, 0, self._n - 1, ql, qr)

    # 获取 a[i] 的值
    # 时间复杂度 O(log n)
    def get(self, i: int) -> int:
        return self._query(1, 0, self._n - 1, i, i)
class Solution:
    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
        """
        思路：和3479类似，在于开始查找方式不同
        对于queries[i] = [ai, bi],固定ai<b2,如果不满足(ai>b2)则交换，因为本题关心的是两个人的位置，交换了也不影响解雇
        如果heights[ai]<heights[bi]:那么直接将heights[ai]移动到heights[bi]即可，结果就是heights[bi]
        如果heights[ai]>heights[bi]:那么找[bi,len),中，第一个大于等于heights[n]>heights[ai]的数，n即为结果
        :param heights:
        :param queries:
        :return:
        """
        t = SegmentTree(heights)
        ans = [-1] * len(queries)
        for i,querie in enumerate(queries):
            #固定左边是小
            if querie[0]>querie[1]:
                temp = querie[0]
                querie[0] = querie[1]
                querie[1] = temp
            elif querie[0]==querie[1]:
                #相等不需要移动
                ans[i] = querie[0]
                continue
            if heights[querie[0]] <= heights[querie[1]]:
                #直接移动到querie[1]即可
                ans[i] = querie[1]
            else:
                #找querie[1]后第一个>=heights[querie[0]]的数
                ans[i] = t.querFirstLarge(querie[1],len(heights)-1,heights[querie[0]])
        return ans
if __name__ == '__main__':
    print(Solution().leftmostBuildingQueries([6,4,8,5,2,7], [[0,1],[0,3],[2,4],[3,4],[2,2]])) #[2,5,-1,5,2]
